#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * compute: C = AB
 * input: A - 4x4
 *        B - 4x4
 *        C - 4x4
 */
static void multiply(int* A, int* B, int* C)
{
    C[0] = A[0]*B[0] + A[1]*B[2];
    C[1] = A[0]*B[1] + A[1]*B[3];
    C[2] = A[2]*B[0] + A[3]*B[2];
    C[4] = A[2]*B[1] + A[3]*B[3];
}

static void xpower(int* A, int n, int* _r)
{
    if (1 == n) {
	memcpy(_r, A, 4*sizeof(int));
	return;
    }

    int tmp[4];
    memcpy(tmp, A, 4*sizeof(int));
    for (int i = 2; i < n; ++i) {
	multiply(tmp, A, _r);
	memcpy(tmp, _r, 4*sizeof(int));
    }
}

int fibonacci(int n)
{
    int A[4] = {1, 1, 1, 0};
    int result[4] = {0};
    
    if (n < 0)
	return -1;
    else if (n > 0)
	xpower(A, n, result);

    return result[0];
}

int fibonacci_r(int n)
{
    if (n < 0)
	return -1;
    if (n < 2)
	return n;
    else
	return fibonacci_r(n-1) + fibonacci_r(n-2);
}

int main(int argc, char *argv[])
{
    int n;
    
    if (argc != 2)
	n = 10;
    else
	n = atoi(argv[1]);

    /* int f = fibonacci_r(n); */
    int f = fibonacci(n);
    printf("f(%d) = %d\n", n, f);

    exit(0);
}
